
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1686. -- [Usaco2005 Open]Waves -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1686: [Usaco2005 Open]Waves</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>8&nbsp;&nbsp;<span class=green>Solved: </span>7<br>[<a href='submitpage.php?id=1686'>Submit</a>][<a href='problemstatus.php?id=1686'>Status</a>][<a href='bbs.php?id=1686'>Discuss</a>]</center><h2>Description</h2><div class=content>
Farmer John's cows thoroughly enjoy throwing pebbles into the lake
next to their grazing field. When a pebble hits the surface of the
lake, it generates a wave that propagates across the surface of the
lake.

The surface of the lake is represented by a large grid of squares.
The water at each square is at some depth, which is determined by
the interaction of the waves.  Before any pebbles are dropped, every
square (except those on the original river banks) has a depth of
0.  When displayed, each square will be represented as follows:

     o Square has a depth < 0
     - Square has a depth = 0
     * Square has a depth > 0
     X Square is part of the original river bank

When a pebble in dropped into the lake it causes a wave of raised
water to spread out in a diamond pattern that grows every second.
The depth of each square in the diamond is increased by 1 for just
one single second. This wave is followed two seconds later by a
wave of lowered water (depth decreased by 1) which also spreads out
as a diamond.  Each pebble causes only two waves, the raised wave
followed by the lowered wave.

For example, the diagram below shows the effect of a pebble dropped
in the middle of the lake at time intervals of 0, 1, 2 and 3 seconds:
after it is dropped:

0 seconds   1 second    2 seconds   3 seconds
 -------     -------     -------     ---*---
 -------     -------     ---*---     --*-*--
 -------     ---*---     --*-*--     -*-o-*-
 ---*---     --*-*--     -*-o-*-     *-o-o-*
 -------     ---*---     --*-*--     -*-o-*-
 -------     -------     ---*---     --*-*--
 -------     -------     -------     ---*---

The river banks have fixed x co-ordinates and run for the entire
length (top to bottom) of the lake with a width of a single square.
When a wave reaches a river bank, rather than carrying on, it
continues to grow but the part that hits the bank is reflected.

The early seconds of a wave hitting one of the river banks are shown
below. To make the picture clearer, the second wave of lowered water
is not shown:

1 second    2 seconds   3 seconds   4 seconds   5 seconds
 X------     X------     X--*---     X-*-*--     X*---*-
 X------     X--*---     X-*-*--     X*---*-     X*----*
 X--*---     X-*-*--     X*---*-     X*----*     X-*----
 X-*-*--     X*---*-     X*----*     X-*----     X--*---
 X--*---     X-*-*--     X*---*-     X*----*     X-*----
 X------     X--*---     X-*-*--     X*---*-     X*----*
 X------     X------     X--*---     X-*-*--     X*---*-

When sections of waves meet they have no effect on the way each
other propagates. In other words, at the next clock tick the waves
will grow as though there was no encounter. Note however that their
effects are combined on the lake.  For example:

 1 second      2 seconds     3 seconds     4 seconds
 ---------     ---------     ---------     ---*-----
 ---------     ---------     ---*-----     --*-*-*--
 ---------     ---*-----     --*-*-*--     -*-o-*-*-
 ---*-----     --*-*-*--     -*-o-*-*-     *-o-----*
 --*-*-*--     -*-o-*-*-     *-o-----*     -o-*-o---
 ---*-----     --*-*-*--     -*-o-*-*-     *-o-----*
 ---------     ---*-----     --*-*-*--     -*-o-*-*-
 ---------     ---------     ---*-----     --*-*-*--
 ---------     ---------     ---------     ---*-----

Write a program to help the cows figure out how the waves will
spread out over time.

</div><h2>Input</h2><div class=content>* Line 1: Four space-separated integers: P, B1, B2, and R:

      * P (1 <= P <= 5) indicates the number of pebbles,<br>

      * B1 (-500,000 <= B1 <= 500,000) and B2 (-500,000 <= B2 <= 500,000)
        are the x co-ordinates of two river banks, and<br>

      * R (1 <= R <= 500,000) the time at which you are to display the lake.<br>

      No two pebbles will be dropped at the same position at the
      same time.  The two banks will have different x co-ordinates,
      and no pebble will be dropped on a bank.

* Lines 2..P+1: Each line contains three space-separated integers that
        describe a pebble: X (-500,000 <= X <= 500,000), Y (-500,000
        <= Y <= 500,000), and and T (1 <= T <= 500,000)

      * X and Y are the coordinates where a pebble is dropped

      * T is the time at which the pebble is dropped

</div><h2>Output</h2><div class=content>* Lines 1..9: The output contains a 9 x 9 grid, centered on 0,0. The
        bottom left of the grid represents (-4, -4) and the top right
        represents (4,4). The grid should represent the state of the
        lake at time R.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>2 4 100 4<br />
-3 0 1<br />
0 0 2<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
--------X<br />
-*------X<br />
*-*-*---X<br />
-o-*-*--X<br />
o-----*-X<br />
-o-*-*--X<br />
*-*-*---X<br />
-*------X<br />
--------X</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1686'>Submit</a>][<a href='problemstatus.php?id=1686'>Status</a>][<a href='bbs.php?id=1686'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
